package leetcode.L500;

import java.util.Arrays;
/*本题使用双指针的思路，首先对数组排序，用一个遍历，加一个双指针左右缩进的方法来逼近正确的值，复杂度为N2*/
public class EX16_ThreeSumClosest {
    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int best = 100000;
        for(int i=0;i<n;i++){
            int j =i+1,k = n-1;
            while(j<k){
                int sum=nums[i]+nums[j]+nums[k];
                if (sum==target)
                    return sum;
                if(Math.abs(sum-target)<Math.abs(best-target)){
                    best = sum;
                }
                if (sum>target){
                    k--;
                }
                else{
                    j++;
                }
            }
        }
        return best;
    }

    public static void main(String[] args) {
        int[] nums={-1,2,1,-4};
        int t=1;
        int r=threeSumClosest(nums,t);
        System.out.println(r);


    }
}
